import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class Tree <T extends Comparable<T>>{
    public Node root;
    Tree(){
        root=null;
    }

    public void Print(){
        Queue<Node> queue=new LinkedList<Node>();
        queue.offer(root);
        while (!queue.isEmpty()){
            Node temp =queue.poll();
            System.out.print(temp.value);
            System.out.print(" ");
            if (temp.left!=null){
                queue.offer(temp.left);
            }
            if (temp.right!=null){
                queue.offer(temp.right);
            }
        }
        System.out.println();
    }
    public void insert(T val){
        Node<T> newNode =new Node<T>(val);
        Node<T> temp =root;
        if(temp==null){
            root=newNode;
        }else{
            while (temp!=null){
                if(val.compareTo(temp.value)==0){
                    break;
              }else if(val.compareTo(temp.value)<0){
                    if(temp.left!=null){
                        temp=temp.left;
                    }else {
                        temp.left=newNode;
                        break;
                    }
                }else {
                    if (temp.right!=null){
                        temp=temp.right;
                    }else {
                        temp.right=newNode;
                        break;
                    }
                }
            }
        }
    }
    public boolean search(T val){
        if(root == null){
            return false;
        }
        Node<T> temp=root;
        while (temp!=null){
            if (val.compareTo(temp.value)==0){
                return true;
            }else if(val.compareTo(temp.value)<0){
                temp =temp.left;
            }else {
                temp =temp.right;
            }
        }
        return false;
    }

    public void delete(T val){
        if(root == null){
            return ;
        }

        Node<T> parent = root;
        Node<T> current = root;

        //查找要删除的点，一个停留在目标节点的父节点，一个指向目标结点
        while(current != null){
            if((val.compareTo(current.value) == 0)){
                break;
            }
            else if(val.compareTo(current.value) < 0){
                parent = current;
                current = current.left;
            } else {
                parent = current;
                current = current.right;
            }
        }

        if(current != null){
            // 要删除的点在叶子节点上
            if(current.left == null && current.right == null){
                // 1.1 root case
                if(current == root){
                    root = null;
                }
                // 1.2 non root case
                else if(parent.left == current){
                    parent.left = null;
                } else {
                    parent.right = null;
                }
            }//
            // 只有一个孩子结点
            else if (current.left == null || current.right == null){
                // 判断目标结点在什么位置，根据具体位置将孩子结点向上平移即可
                if(current == root){
                    if(current.left != null){
                        root = current.left;
                    } else {
                        root = current.right;
                    }
                } else if (parent.left == current) {
                    if(current.left != null){
                        parent.left = current.left;
                    }else {
                        parent.left = current.right;
                    }
                } else {
                    if(current.left != null){
                        parent.right = current.left;
                    }else {
                        parent.right = current.right;
                    }
                }
            }
            // 有两个孩子结点
            else {
                // 找到左子树最大的数替代目标结点
                Node<T> leftRoot = current.left;
                T maxVal = findLeftMaxAndDelete(leftRoot);
                current.value = maxVal;
            }

        }


    }

    private T findLeftMaxAndDelete(Node<T> root){
        Node<T> temp = root;
        Node<T> parent = root;
        while(temp != null && temp.right!=null){
            parent = temp;
            temp = temp.right;
        }

        // delete
        if(temp != null){
            parent.right = null;
            return temp.value;
        } else {
            return null;
        }


    }
    //前序遍历

    public static void preOrderRe(Node biTree) {
        System.out.println(biTree.value);
        Node leftTree = biTree.left;
        if(leftTree != null)
        {
            preOrderRe(biTree.left);
        }
        Node rightTree = biTree.right;
        if(rightTree != null)
        {
            preOrderRe(rightTree);
        }
    }
    //中序遍历
    public static void midOrderRe(Node biTree) {
        if(biTree == null)
            return;
        else
        {
            midOrderRe(biTree.left);
            System.out.println(biTree.value);
            midOrderRe(biTree.right);
        }
    }
    //后序遍历
    public static void postOrderRe(Node biTree)
    {//后序遍历递归实现
        if(biTree == null)
            return;
        else
        {
            postOrderRe(biTree.left);
            postOrderRe(biTree.right);
            System.out.println(biTree.value);
        }
    }

}